--[[
    @desc 优化的栈 下标由0到n-1  优化点：查找里面的元素时可实现查找时间复杂度为0(1)
    @author zch
    @data:2022-04-20 14:00:00
]]

local IndexStack = IndexStack or BaseClass()
local table_insert = table.insert
local table_remove = table.remove
local setmetatable = setmetatable

function IndexStack:__init()
	self.size = 0
	self.items = {}
    self.item_dic = {}
    -- setmetatable(self.item_dic, {__mode = "k"})
end

-- @brief 栈顶插入一个值 这里假设item是表或者是函数或是userdata才能用tostring的方法，如果是数字或者bool或者字符就改用其他方法
function IndexStack:Push(item)
	self.size = self.size + 1
	self.items[self.size] = item
    -- self.item_dic[item] = self.size
	self.item_dic[tostring(item)] = self.size
end

-- 栈顶移除一个值 并返回
function IndexStack:Pop()
	if self.size > 0 then
		local item = self.items[self.size]
		self.items[self.size] = nil
		self.size = self.size - 1
        -- self.item_dic[item] = nil
		self.item_dic[tostring(item)] = nil
		return item
	end
	return nil
end

-- 栈顶获得一个值 并返回
function IndexStack:Peek()
	if self.size > 0 then
		local item = self.items[self.size]
		return item
	end
	return nil
end

-- @brief 实现了查找时间复杂度为O(1)
function IndexStack:Contains(item)
    -- return self.item_dic[item] ~= nil
	return self.item_dic[tostring(item)] ~= nil
end

function IndexStack:Clear()
	self.size = 0
	self.items = {}
    self.item_dic = {}
end

function IndexStack:GetSize()
	return self.size
end

function IndexStack:IsEmpty()
	return self.size <= 0
end

return IndexStack